package codingforgreat.lchot150;

public class Lc037 {
    public void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][] slot = new boolean[9][10];
        initMap(board,row,col,slot);
        process(board,0,0,row,col,slot);
    }
    public void initMap(char[][] board,boolean[][] row,boolean[][] col,boolean[][] slot){
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                int s = 3*(i/3) + (j/3);
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    slot[s][num] = true;
                }
            }
        }
    }
    public boolean process(char[][] board,int i,int j,boolean[][] row,boolean[][] col,boolean[][] slot){
        if(i == 9){
            return true;
        }
        int nexti = j == 8 ? i + 1: i;
        int nextj = j == 8 ? 0 : j + 1;
        if(board[i][j] != '.'){
            return process(board,nexti,nextj,row,col,slot);
        } else{
            int s = 3*(i/3) + (j/3);
            //尝试1-9
            for(int num = 1;num <= 9;num++){
                if(!row[i][num] && !col[j][num] && !slot[s][num] ){
                    board[i][j] = (char) (num + '0');
                    row[i][num] = true;
                    col[j][num] = true;
                    slot[s][num] = true;
                    if(process(board,nexti,nextj,row,col,slot)){
                        return true;
                    }
                    board[i][j] = '.';
                    row[i][num] = false;
                    col[j][num] = false;
                    slot[s][num] = false;
                }
            }
        }
        return false;
    }
}
